package 链表;

import java.util.Deque;
import java.util.LinkedList;

//https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=295&tqId=722&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
public class BM3_链表中的节点每k个一组翻转 {

	public static void main(String[] args) {
		ListNode node5 = new ListNode(5);
		ListNode node4 = new ListNode(4);
		ListNode node3 = new ListNode(3);
		ListNode node2 = new ListNode(2);
		ListNode node1 = new ListNode(1);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;

		BM3_链表中的节点每k个一组翻转 test = new BM3_链表中的节点每k个一组翻转();
		ListNode ret = test.reverseKGroup(node1, 3);
		System.out.println(ret.toString());
	}

	public ListNode reverseKGroup(ListNode head, int k) {
		if (head == null)
			return head;
		Deque<ListNode> deque = new LinkedList<>();
		ListNode newHead = new ListNode(-1);
		ListNode now = newHead;
		int cnt = k;
		while (head != null) {
			if (cnt != 0) {
				deque.push(head);
				cnt--;
				head = head.next;
			}
			if (deque.size() == k) {
				while (!deque.isEmpty()) {
					now.next = deque.pop();
					now = now.next;
					now.next = null;
				}
				cnt = k;
			}
		}
		if (cnt != 0) {
			while (!deque.isEmpty()) {
				now.next = deque.pollLast();
				now = now.next;
				now.next = null;
			}
		}
		return newHead.next;
	}

	public ListNode reverseKGroup01(ListNode head, int k) {
		// 找到每次翻转的尾部
		ListNode tail = head;
		for (int i = 0; i < k; i++) {
			if (tail == null) {
				// 如果不足k到了链表尾，直接返回，不翻转
				return head;
			}
			tail = tail.next;
		}
		// 翻转时需要的前序和当前节点
		ListNode pre = null;
		ListNode cur = head;
		// 在到达当前段尾节点前
		while (cur != tail) {
			ListNode temp = cur.next;
			cur.next = pre;
			pre = cur;
			cur = temp;
		}
		// 当前尾指向下一段要翻转的链表
		head.next = reverseKGroup(tail, k);
		return pre;
	}
}
